{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduction to Graph Matching"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The graph matching problem (GMP), is meant to find an alignment of nodes between two graphs that minimizes the number of edge disagreements between those two graphs. Therefore, the GMP can be formally written as an optimization problem: \n",
    "\n",
    "\\begin{equation}\n",
    "\\begin{aligned}\n",
    "\\min & {\\;-\\text{trace}(APB^T P^T)}\\\\\n",
    "\\text{s.t. } & {\\;P \\: \\epsilon \\: \\mathcal{P}} \\\\\n",
    "\\end{aligned}\n",
    "\\end{equation}\n",
    "\n",
    "Where $\\mathcal{P}$ is the set of possible permutation matrices.\n",
    "\n",
    "The Quadratic Assignment problem is a combinatorial opimization problem, modeling following the real-life problem: \n",
    "\n",
    "\"Consider the problem of allocating a set of facilities to a set of locations, with the\n",
    "cost being a function of the distance and flow between the facilities, plus costs associated\n",
    "with a facility being placed at a certain location. The objective is to assign each facility\n",
    "to a location such that the total cost is minimized.\" [1]\n",
    "\n",
    "When written as an optimization problem, the QAP is represented as:\n",
    "\n",
    "\\begin{equation}\n",
    "\\begin{aligned}\n",
    "\\min & {\\; \\text{trace}(APB^T P^T)}\\\\\n",
    "\\text{s.t. } & {\\;P \\: \\epsilon \\: \\mathcal{P}} \\\\\n",
    "\\end{aligned}\n",
    "\\end{equation}\n",
    "\n",
    "Since the GMP objective function is the negation of the QAP objective function, any algorithm that solves one can solve the other. \n",
    "\n",
    "\n",
    "This class is an implementation of the Fast Approximate Quadratic Assignment Problem (FAQ), an algorithm designed to efficiently and accurately solve the QAP, as well as GMP. \n",
    "\n",
    "[1] Optimierung, Diskrete & Er, Rainer & Ela, A & Burkard, Rainer & Dragoti-Cela, Eranda & Pardalos, Panos & Pitsoulis, Leonidas. (1998). The Quadratic Assignment Problem. Handbook of Combinatorial Optimization. 10.1007/978-1-4613-0303-9_27. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from graspologic.match import graph_match\n",
    "from graspologic.simulations import er_np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For the sake of this tutorial, we will use FAQ to solve the GMP for two graphs where we know a solution exists. \n",
    "Below, we sample a binary graph (undirected and no self-loops) $G_1 \\sim ER_{NP}(50, 0.3)$.\n",
    "Then, we randomly shuffle the nodes of $G_1$ to initiate $G_2$.\n",
    "The number of edge disagreements as a result of the node shuffle is printed below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "n = 50\n",
    "p = 0.3\n",
    "\n",
    "np.random.seed(1)\n",
    "G1 = er_np(n=n, p=p)\n",
    "node_shuffle_input = np.random.permutation(n)\n",
    "G2 = G1[np.ix_(node_shuffle_input, node_shuffle_input)]\n",
    "print(\"Number of edge disagreements: \", np.sum(abs(G1-G2)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Visualize the adjacency matrices"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from graspologic.plot import heatmap\n",
    "\n",
    "heatmap(G1, cbar=False, title = 'G1 [ER-NP(50, 0.3) Simulation]')\n",
    "_ = heatmap(G2, cbar=False, title = 'G2 [G1 Randomly Shuffled]')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Below, we solve the GMP using the `graph_match` function. The number of edge disagreements after optimization is printed below. With zero edge disagreements, we see that FAQ is successful in unshuffling the graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "_, perm_inds, score, misc = graph_match(G1, G2)\n",
    "G2 = G2[perm_inds][:, perm_inds] # permute both rows and columns to preserve adjacency\n",
    "print(\"Number of edge disagreements: \", np.sum(abs(G1-G2)))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.9.7 ('.venv': poetry)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.7"
  },
  "vscode": {
   "interpreter": {
    "hash": "bc13b1df6b0248aaf34f3e7f5790740f6f355623370613abc0a11b70d06c20f2"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
